/*
 * @lc app=leetcode.cn id=77 lang=typescript
 *
 * [77] 组合
 */

// @lc code=start
function combine(n: number, k: number): number[][] {
  const ans: number[][] = [];
  const dfs = (num: number, count: number, buff: number[]) => {
    if (count === k) {
      ans.push([...buff]);
      return;
    }
    // 剩下的数字数量不够补充剩下的位置
    if (n - num + 1 < k - count) return;
    buff[count] = num;
    // 选择当前数字
    dfs(num + 1, count + 1, buff);
    // 不选择当前数字
    dfs(num + 1, count, buff);
  };
  dfs(1, 0, []);
  return ans;
}
// @lc code=end
